Automated integrated circuit design has traditionally addressed placement and routing as independent and separable processes. For example, a circuit placement process may place all of the required circuit elements or blocks of the integrated circuit in a layout, and then a routing process subsequently attempts to layout signal and power lines to interconnect the circuit blocks with each other and with I/O terminals. While this approach may suffice for layout of many purely digital circuits, separate placement and routing processes have serious shortcomings for generation of analog, mixed-signal, or custom digital circuit layouts. In fact, the deficiencies are generally so severe in analog and mixed-signal design that adoption of automated routing for these types of circuits has been limited. In particular, automated layout of analog and mixed signal circuits has typically been restricted to circuit block connect-up at higher levels in the circuit hierarchy, rather than the device level layout where benefits of automated routing could potentially have the most impact on productivity.
A significant complication in contemporary integrated circuit design for digital, analog, and mixed signal circuits is the complexity of process technology design rules with which layout construction must comply. These complex design rules cause computational challenges at all levels of the design hierarchy but are particularly troublesome at lower-levels in the design hierarchy where one must deal with a large amount of geometrical complexity due to primitive devices (e.g., MOSFETs, resistors, and bipolar transistors), dense highly-structured interconnected groups of primitives (e.g., abutted devices, matching patterns, and arrays), device-level physical pins (e.g., for making routing connections to device-level features), substrate and well contacts, contacts rings, wells, and other low-level geometrical constructs necessary for building electrically and physically valid integrated circuits. The geometrical complexity involved at these levels is one reason why traditional place and route approaches that completely decouple the placement and routing phases of construction may fail entirely or result in layouts of inferior quality.